package edu.dayu.demo3;

/**
 * 有一个只含有 'Q', 'W', 'E', 'R' 四种字符，且长度为 n 的字符串。
 * 假如在该字符串中，这四个字符都恰好出现 n/4 次，那么它就是一个「平衡字符串」。
 * 输入：s = "QQWE"
 * 输出：1
 * 解释：我们需要把一个 'Q' 替换成 'R'，这样得到的 "RQWE" (或 "QRWE") 是平衡的。
 *
 * 思路：首先字符串长度是四的倍数，要求每个字符有 四分之一个。
 *      1、有一个很简单的思路，求出大于平均数的字符个数，然后减去 len/4 即可。
 *      思路有问题，题意是修改一个连续字串使得成为一个平衡的。
 *      2、 首先记录，每个字符出现的个数
 *      然后用滑动窗口，只要窗口外面的字符串没有超过 len/4 的，就说明当前窗口可以满足条件，然后缩小窗口。
 *
 */
public class 替换子串得到平衡字符串 {
    public static void main(String[] args) {
        String s = "WWEQERQWQWWRWWERQWEQ";
        System.out.println(balancedString(s));
    }

    public static int balancedString(String s) {
        int[] cnt = new int[26];
        // 统计字符出现的次数
        for (char c : s.toCharArray()) cnt[c - 'A']++;
        int n = s.length(), m = n / 4;
        // 若四个字符都恰好出现n/4次，则是平衡字符串
        if (cnt['Q'-'A'] == m && cnt['W'-'A'] == m && cnt['E'-'A'] == m && cnt['R'-'A'] == m)
            return 0;
        // 滑动窗口 + 双指针
        int res = n, l = 0, r = 0;
        /**
         移动指针r，对应字符次数减1，若此时四个字符串出现次数均小于等于平均值
         说明替换当前区间子字符串可以使其成为平衡字符串
         计算最小操作数，并移动l指针缩小可取范围
         QWRR
         */
        while (r < n) {
            cnt[s.charAt(r++) - 'A']--;
            while (cnt['Q'-'A']<=m && cnt['W'-'A']<=m && cnt['E'-'A']<=m && cnt['R'-'A']<=m) {
                res = Math.min(res, r - l);
                cnt[s.charAt(l++) - 'A']++;
            }
        }
        return res;
    }

}
